package arithmetic;

/**
 * @Author: Jie
 * @Date: 2019/1/23 10:29
 * @Function :leetcode 50 实现 pow(x, n) ，即计算 x 的 n 次幂函数。
 *
 * 说明:
 *
 * -100.0 < x < 100.0
 * n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
 */
public class A_11_PowXy {
    public static void main(String[] args) {
        System.out.println("1&1=="+(1&1));
        System.out.println(-2%2);
        System.out.println("while org result:== "+myPowOrg(3,4));

//        System.out.println(5/3);
//        System.out.println(-5/3);

        //指数的的幂是整数就不用考虑 小数问题
        System.out.println(Integer.MIN_VALUE+"  "+Integer.MAX_VALUE);
        double num = 2;
//        int mi = -3;
//        int mi = -2147483648;//int 最小值
//        -2^31——2^31-1,即-2147483648——2147483647 1、对于正数来说,它的补码就是它本身
//        int mi = -21474565;
//        int mi = -10;
        int mi = 7;
        double result = 0;
        //1、公式方法
//        result=Math.pow(num,mi);
        //2
//        result = myPow2(num,mi);
        System.out.println("**********print result=="+result);

//        result = myPow4(num,mi);

        result = myPow5(2, -9);
        System.out.println("print result=="+result);
    }


    /**
     *  TODO While 官方，已解析.位运算
     *
     * x==3  n==4
     * n==4  temp==3
     * n==2  temp==9
     * n==1  temp==81
     * n==1  res *= temp res:1  temp:81
     * while org result:== 81.0
     *
     * x==3  n==3
     * n==3  temp==3
     * n==3  res *= temp res:1  temp:3
     * n==1  temp==9
     * n==1  res *= temp res:3  temp:9
     * while org result:== 27.0
     *
     * x==3  n==5
     * n==5  temp==3
     * n==5  res *= temp res:1  temp:3
     * n==2  temp==9
     * n==1  temp==81
     * n==1  res *= temp res:3  temp:81
     * while org result:== 243.0
     *
     * x==3  n==7
     * n==7  temp==3
     * n==7  res *= temp res:1  temp:3
     * n==3  temp==9
     * n==3  res *= temp res:3  temp:9
     * n==1  temp==81
     * n==1  res *= temp res:27  temp:81
     * while org result:== 2187.0
     */
    private static double myPowOrg(int x, int n) {
        int res=1,temp=x;
        System.out.println( "x=="+x+"  n=="+n);
        if(n == 0) { return 1.0; }
        while (n>0){
            System.out.println("n=="+n+"  temp=="+temp);
            if ((n & 1)==1){
                System.out.println("n=="+n+"  res *= temp res:"+res+"  temp:"+temp);
                res = res * temp;
//                res *= temp;//当为n 为偶数时，
//                只有当最后被除尽 4/4时，所有的结果都会 由temp（81）--》res;

//                res *= temp;//当n 为奇数是，
//                第一次 res = temp;当被除尽时， eg: n== 5 2 1 ,res = temp（3） *temp（81）(之前累成)
            }
            n= n>>1;
            temp *=temp;
        }
        return  res;
    }

    // TODO: 2019/3/14 leetcode 最快 8ms
    /**
     *   if(n == 0) return 1.0;
     *      double d = myPow(x, n/2);
     *      if(n%2 == 0) return d*d;
     *      if(n < 0) return d*d*(1/x);
     *      return d*d*x;
     * @param x
     * @param n
     * @return
     */
    public static double myPow5(double x, int n) {
//        System.out.println("myPow times x=="+x+" n=="+n);
        if(n == 0) return 1.0;
        double d = myPow5(x, n/2);
        if(n%2 == 0) {
//            System.out.println("n%2==0 x=="+x+" n=="+n+" d=="+d+" d*d="+(d*d));
            return d*d;
        }
        if(n < 0) {
            //TODO 如果是负数，那么递归结束前 0 -->0 -1 -2  ,肯定必须执行-1 ，即（1/x） 。那么，n%2 == 0 时只会执行 1/x 的幂，
            //TODO 这个函数 代替了 d*d*x 当 n<0 时
            // TODO 结果：当 n<0  且 n%2 != 0 时， 都会在此 （1/x）
//            System.out.println("n<0  x=="+x+" n=="+n+" d=="+d+" (1/x)="+(1/x)+"  d*d*(1/x)=="+d*d*(1/x));
            return d*d*(1/x);
        }
//        System.out.println("d*d*x  x=="+x+" n=="+n+" d=="+d+" d*d*x="+(d*d*x));
        return d*d*x;
    }

    //TODO 正确答案1 非递归 没哟搞懂？？？
    private static double myPow4(double x, int n) {
        double res = 1.0;
        for(int i = n; i != 0; i /= 2){//从 n->0
            System.out.println( "result n=="+i);//if 7 3 1
            if(i % 2 != 0){//指数幂运算累 成
                res *= x;
                System.out.println( "result i % 2 != 0=="+res);
            }
            x *= x;
            System.out.println( "result x *= x=="+x);
        }
        return  n < 0 ? 1 / res : res;
    }

    //TODO 递归官方 没哟搞懂？？？
     /**
     * 1、简单 递归 O（n）
     * 2、分治 算法 O (log2 n)
     *  pow x y
     *  =(pow x y/2 ) *  (pow x y/2 )
     *  TODO 递归官方
     */
    private static double myPow2(double x, int n) {
        System.out.println( "x=="+x+"  n=="+n);
        if(n == 0) { return 1.0; }
        double d = myPow2(x, n/2);
        System.out.println( "result d=="+d);
        if(n%2 == 0) {
            System.out.println( "result n%2=="+d*d);
            return d*d;
        }
        if(n < 0) {     //TODO 递归官方 没哟搞懂？？？
            System.out.println( "result n < 0=="+d*d*(1/x));
            return d*d*(1/x);
        }
        System.out.println( "result d*d*x=="+d*d*x);
        return d*d*x;
    }

    // TODO 正确答案 自写第一次递归算法 int 最小值取反
    private static double myPow(double x, int n) {
        //结束条件
        if (n == 0){
            return 1.0;
        }
        //递归条件
            if (n<0){//        -2^31——2^31-1,即-2147483648——2147483647 1、对于正数来说,它的补码就是它本身
            //todo 如果 n 为int 最小值 -n 则超过int型最大值。 java.lang.StackOverflowError
                if (n!=Integer.MIN_VALUE){
                    return 1 / myPow(x,-n);
                }else {
                    return 1/ (x * myPow(x,Integer.MAX_VALUE));
                }
            }
            //奇数 -1 相城
        double v = myPow(x, n  / 2);
         if(n%2 == 0){
             return v * v; //处理递归后返回结果
         }else {
                return v * v * x; //处理递归后返回结果
         }
    }


    //success 0ms, 2024 年 04 月 09 日 15:45:42
    public double myPow0(double x, int n) {
//        if (n==0)return 1.0;
//
//        if (n<0){
//            return 1.0/myPow(x,-n);
//        }
//        double res = myPow(x,n/2);
//        if (n%2==0){
//            return res * res;
//        }
//        return x * res * res;
        return mPow(x,n);
    }
    //int n ----> long n .. Integer.min-->MAX 越界！！！
    public double mPow(double x,long n){
        if (n==0)return 1.0;
        if (n<0){
            return 1.0/mPow(x,-n);
        }
        double res = mPow(x,n/2);
        if (n%2==0){
            return res * res;
        }
        return x * res * res;
    }
}
